Tyulenvev được sinh ra trong một gia đình quân nhân ở khu định cư Simbirsk (nay là Ulyanovsk Oblast) của Shatrashany. Ông làm việc trong các nhà máy và là một ngư dân biển Caspi trước khi được đưa vào Quân đội Hoàng gia Nga vào năm 1913. Trong Thế chiến thứ nhất, ông được trao tặng Huân chương Thánh George vì lòng dũng cảm.

Tyulenvev gia nhập Hồng quân sau cuộc cách mạng và phục vụ trong Nội chiến Nga ở Tập đoàn quân kỵ binh 1. Ông cũng tham gia đàn áp cuộc nổi loạn Kronstadt và trong Chiến tranh Liên Xô - Ba Lan. Năm 1939, ông chỉ huy Tập đoàn quân 12 trong cuộc xâm chiếm Ba Lan của Liên Xô. Ông được thăng cấp Đại tướng năm 1940.

Khi Chiến tranh Xô-Đức bùng nổ vào tháng 6 năm 1941, ông phụ trách Quân khu Moskva. Trong ba tháng đầu của cuộc chiến, Tyulenev chỉ huy Phương diện quân Nam. Trong phần còn lại của cuộc chiến, ông là chỉ huy Quân khu Zakavkaz và Phương diện quân Zakavkaz. Tyulenev là tác giả của một số cuốn sách hồi ức, bao gồm Kỵ binh Liên Xô chiến đấu vì Tổ quốc (1957) và Qua ba cuộc chiến (năm 1972).